package Algorithm.LinkedListProblem;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author cj
 * @Date 2021/12/23 20:06
 */
public class copyListWithRand {

    static class Node {
        public int value;
        public Node next;
        public Node rand;

        public Node(int val) {
            this.value = val;
        }
    }

    public static Node copyListWithRand1(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }
        return map.get(head);
    }

    public static Node copyListWithRand2(Node head) {
        Node cur = head;
        while (cur != null) {
            Node realNext = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = realNext;
            cur = realNext;
        }
        cur = head;
        while (cur != null) {
            Node copyNode = cur.next;
            copyNode.rand = cur.rand != null ? cur.rand.next : null;
            cur = cur.next.next;
        }
        // 分离
        cur = head;
        Node res = head.next;
        while (cur != null) {
            Node copyNode = cur.next;
            cur.next = copyNode.next;
            copyNode.next = cur.next.next;
            cur = cur.next.next;
        }
        return res;
    }
}
